{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## 数论 数学",
   "id": "f7486dcc65935cfc"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "MODE = 10**9 + 7\n",
    "\n",
    "def product(m1, m2):\n",
    "    # 矩阵乘法\n",
    "    assert len(m1[0]) == len(m2), \"Matrix dimensions do not match for multiplication\"\n",
    "    n, m, p = len(m1), len(m2), len(m2[0])\n",
    "    ans = [[0] * p for _ in range(n)]\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            for k in range(p):\n",
    "                ans[i][k] = (ans[i][k] + m1[i][j] * m2[j][k]) % MODE\n",
    "    return ans\n"
   ],
   "id": "b179c097e54a216b"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-10-21T09:49:38.192537Z",
     "start_time": "2025-10-21T09:49:38.184960Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# 快速幂\n",
    "def pow_mat(f0,f1,nn):\n",
    "    base = [[1,0],[0,1]]  # 单位矩阵\n",
    "    t = [[1,1],[1,0]]     # 递推转移矩阵\n",
    "    while nn:\n",
    "        if nn & 1:\n",
    "            base = product(base, t)\n",
    "        t = product(t, t)\n",
    "        nn >>= 1\n",
    "    return product(base, [[f1],[f0]])  # 取[1][0] 得到fn\n"
   ],
   "id": "d7397e74c4bbb288",
   "outputs": [],
   "execution_count": 1
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
